home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 14 / CU Amiga Magazine's Super CD-ROM 14 (1997)(EMAP Images)(GB)(Track 1 of 3)[!][issue 1997-09].iso / CUCD / Programming / Mesa-2.2 / src / clip.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-03-13  |  28.8 KB  |  1,000 lines
  1. /* $Id: clip.c,v 1.11 1997/02/13 21:16:09 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  2.2
  6.  * Copyright (C) 1995-1997  Brian Paul
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25.  * $Log: clip.c,v $
  26.  * Revision 1.11  1997/02/13 21:16:09  brianp
  27.  * if too many vertices in polygon return VB_SIZE-1, not VB_SIZE
  28.  *
  29.  * Revision 1.10  1997/02/10 21:16:12  brianp
  30.  * added checks in polygon clippers to prevent array overflows
  31.  *
  32.  * Revision 1.9  1997/02/04 19:39:39  brianp
  33.  * changed size of vlist2[] arrays to VB_SIZE per Randy Frank
  34.  *
  35.  * Revision 1.8  1996/12/02 20:10:07  brianp
  36.  * changed the macros in gl_viewclip_polygon() to be like gl_viewclip_line()
  37.  *
  38.  * Revision 1.7  1996/10/29 02:55:02  brianp
  39.  * fixed duplicate vertex bug in gl_viewclip_polygon()
  40.  *
  41.  * Revision 1.6  1996/10/07 23:48:33  brianp
  42.  * changed temporaries to GLdouble in gl_viewclip_polygon()
  43.  *
  44.  * Revision 1.5  1996/10/03 01:43:45  brianp
  45.  * changed INSIDE() macro in gl_viewclip_polygon() to work like other macros
  46.  *
  47.  * Revision 1.4  1996/10/03 01:36:33  brianp
  48.  * changed COMPUTE_INTERSECTION macros in gl_viewclip_polygon to avoid
  49.  * potential roundoff errors
  50.  *
  51.  * Revision 1.3  1996/09/27 01:24:23  brianp
  52.  * removed unused variables
  53.  *
  54.  * Revision 1.2  1996/09/15 01:48:58  brianp
  55.  * removed #define NULL 0
  56.  *
  57.  * Revision 1.1  1996/09/13 01:38:16  brianp
  58.  * Initial revision
  59.  *
  60.  */
  61.  
  62.  
  63. #include <string.h>
  64. #include "clip.h"
  65. #include "context.h"
  66. #include "dlist.h"
  67. #include "macros.h"
  68. #include "matrix.h"
  69. #include "types.h"
  70. #include "vb.h"
  71. #include "xform.h"
  72.  
  73.  
  74.  
  75.  
  76. /* Linear interpolation between A and B: */
  77. #define LINTERP( T, A, B )   ( (A) + (T) * ( (B) - (A) ) )
  78.  
  79.  
  80. #define EYE_SPACE 1
  81. #define CLIP_SPACE 2
  82.  
  83. static GLuint Space;
  84.  
  85.  
  86.  
  87. /*
  88.  * This function is used to interpolate colors, indexes, and texture
  89.  * coordinates when clipping has to be done.  In general, we compute
  90.  *     aux[dst] = aux[in] + t * (aux[out] - aux[in])
  91.  * where aux is the quantity to be interpolated.
  92.  * Input:  dst - index of array position to store interpolated value
  93.  *         t - a value in [0,1]
  94.  *         in - index of array position corresponding to 'inside' vertex
  95.  *         out - index of array position corresponding to 'outside' vertex
  96.  */
  97. static void interpolate_aux( GLcontext* ctx,
  98.                              GLuint dst, GLfloat t, GLuint in, GLuint out )
  99. {
  100.    struct vertex_buffer* VB = ctx->VB;
  101.  
  102.    if (ctx->ClipMask & CLIP_FCOLOR_BIT) {
  103.       VB->Fcolor[dst][0] = LINTERP( t, VB->Fcolor[in][0], VB->Fcolor[out][0] );
  104.       VB->Fcolor[dst][1] = LINTERP( t, VB->Fcolor[in][1], VB->Fcolor[out][1] );
  105.       VB->Fcolor[dst][2] = LINTERP( t, VB->Fcolor[in][2], VB->Fcolor[out][2] );
  106.       VB->Fcolor[dst][3] = LINTERP( t, VB->Fcolor[in][3], VB->Fcolor[out][3] );
  107.    }
  108.    else if (ctx->ClipMask & CLIP_FINDEX_BIT) {
  109.       VB->Findex[dst] = (GLuint) (GLint) LINTERP( t, (GLfloat) VB->Findex[in],
  110.                                                  (GLfloat) VB->Findex[out] );
  111.    }
  112.  
  113.    if (ctx->ClipMask & CLIP_BCOLOR_BIT) {
  114.       VB->Bcolor[dst][0] = LINTERP( t, VB->Bcolor[in][0], VB->Bcolor[out][0] );
  115.       VB->Bcolor[dst][1] = LINTERP( t, VB->Bcolor[in][1], VB->Bcolor[out][1] );
  116.       VB->Bcolor[dst][2] = LINTERP( t, VB->Bcolor[in][2], VB->Bcolor[out][2] );
  117.       VB->Bcolor[dst][3] = LINTERP( t, VB->Bcolor[in][3], VB->Bcolor[out][3] );
  118.    }
  119.    else if (ctx->ClipMask & CLIP_BINDEX_BIT) {
  120.       VB->Bindex[dst] = (GLuint) (GLint) LINTERP( t, (GLfloat) VB->Bindex[in],
  121.                                                  (GLfloat) VB->Bindex[out] );
  122.    }
  123.  
  124.    if (ctx->ClipMask & CLIP_TEXTURE_BIT) {
  125.       /* TODO: is more sophisticated texture coord interpolation needed?? */
  126.       if (Space==CLIP_SPACE) {
  127.      /* also interpolate eye Z component */
  128.      VB->Eye[dst][2] = LINTERP( t, VB->Eye[in][2], VB->Eye[out][2] );
  129.       }
  130.       VB->TexCoord[dst][0] = LINTERP(t,VB->TexCoord[in][0],VB->TexCoord[out][0]);
  131.       VB->TexCoord[dst][1] = LINTERP(t,VB->TexCoord[in][1],VB->TexCoord[out][1]);
  132.       VB->TexCoord[dst][2] = LINTERP(t,VB->TexCoord[in][2],VB->TexCoord[out][2]);
  133.       VB->TexCoord[dst][3] = LINTERP(t,VB->TexCoord[in][3],VB->TexCoord[out][3]);
  134.    }
  135.  
  136. }
  137.  
  138.  
  139.  
  140.  
  141. void gl_ClipPlane( GLcontext* ctx, GLenum plane, const GLfloat *equation )
  142. {
  143.    GLint p;
  144.  
  145.    p = (GLint) (plane - GL_CLIP_PLANE0);
  146.    if (p<0 || p>=MAX_CLIP_PLANES) {
  147.       gl_error( ctx, GL_INVALID_ENUM, "glClipPlane" );
  148.       return;
  149.    }
  150.  
  151.    /*
  152.     * The Equation is transformed by the transpose of the inverse of the
  153.     * current modelview matrix and stored in the resulting eye coordinates.
  154.     */
  155.    if (!ctx->ModelViewInvValid) {
  156.       gl_compute_modelview_inverse(ctx);
  157.    }
  158.    gl_transform_vector( ctx->Transform.ClipEquation[p], equation,
  159.                 ctx->ModelViewInv );
  160. }
  161.  
  162.  
  163.  
  164. void gl_GetClipPlane( GLcontext* ctx, GLenum plane, GLdouble *equation )
  165. {
  166.    GLint p;
  167.  
  168.    if (INSIDE_BEGIN_END(ctx)) {
  169.       gl_error( ctx, GL_INVALID_OPERATION, "glGetClipPlane" );
  170.       return;
  171.    }
  172.  
  173.    p = (GLint) (plane - GL_CLIP_PLANE0);
  174.    if (p<0 || p>=MAX_CLIP_PLANES) {
  175.       gl_error( ctx, GL_INVALID_ENUM, "glGetClipPlane" );
  176.       return;
  177.    }
  178.  
  179.    equation[0] = (GLdouble) ctx->Transform.ClipEquation[p][0];
  180.    equation[1] = (GLdouble) ctx->Transform.ClipEquation[p][1];
  181.    equation[2] = (GLdouble) ctx->Transform.ClipEquation[p][2];
  182.    equation[3] = (GLdouble) ctx->Transform.ClipEquation[p][3];
  183. }
  184.  
  185.  
  186.  
  187.  
  188. /**********************************************************************/
  189. /*                         View volume clipping.                      */
  190. /**********************************************************************/
  191.  
  192.  
  193. /*
  194.  * Clip a point against the view volume.
  195.  * Input:  v - vertex-vector describing the point to clip
  196.  * Return:  0 = outside view volume
  197.  *          1 = inside view volume
  198.  */
  199. GLuint gl_viewclip_point( const GLfloat v[] )
  200. {
  201.    if (   v[0] > v[3] || v[0] < -v[3]
  202.        || v[1] > v[3] || v[1] < -v[3]
  203.        || v[2] > v[3] || v[2] < -v[3] ) {
  204.       return 0;
  205.    }
  206.    else {
  207.       return 1;
  208.    }
  209. }
  210.  
  211.  
  212.  
  213.  
  214. /*
  215.  * Clip a line segment against the view volume defined by -w<=x,y,z<=w.
  216.  * Input:  i, j - indexes into VB->V* of endpoints of the line
  217.  * Return:  0 = line completely outside of view
  218.  *          1 = line is inside view.
  219.  */
  220. GLuint gl_viewclip_line( GLcontext* ctx, GLuint *i, GLuint *j )
  221. {
  222.    struct vertex_buffer* VB = ctx->VB;
  223.    GLfloat (*coord)[4] = VB->Clip;
  224.  
  225.    GLfloat t, dx, dy, dz, dw;
  226.    register GLuint ii, jj;
  227.  
  228.    Space = CLIP_SPACE;
  229.    ii = *i;
  230.    jj = *j;
  231.  
  232. /*
  233.  * We use 6 instances of this code to clip agains the 6 planes.
  234.  * For each plane, we define the OUTSIDE and COMPUTE_INTERSECTION
  235.  * macros apprpriately.
  236.  */
  237. #define GENERAL_CLIP                            \
  238.    if (OUTSIDE(ii)) {                                           \
  239.       if (OUTSIDE(jj)) {                                        \
  240.          /* both verts are outside ==> return 0 */            \
  241.          return 0;                                              \
  242.       }                                                         \
  243.       else {                                                    \
  244.          /* ii is outside, jj is inside ==> clip */             \
  245.      /* new vertex put in position VB->Free */            \
  246.          COMPUTE_INTERSECTION( VB->Free, jj, ii )                     \
  247.      if (ctx->ClipMask)                        \
  248.         interpolate_aux( ctx, VB->Free, t, jj, ii );        \
  249.      ii = VB->Free;                            \
  250.      VB->Free++;                            \
  251.      if (VB->Free==VB_SIZE)  VB->Free = 1;                \
  252.       }                                                         \
  253.    }                                                            \
  254.    else {                                                       \
  255.       if (OUTSIDE(jj)) {                                        \
  256.          /* ii is inside, jj is outside ==> clip */             \
  257.      /* new vertex put in position VB->Free */            \
  258.          COMPUTE_INTERSECTION( VB->Free, ii, jj );                    \
  259.      if (ctx->ClipMask)                        \
  260.         interpolate_aux( ctx, VB->Free, t, ii, jj );        \
  261.      jj = VB->Free;                            \
  262.      VB->Free++;                            \
  263.      if (VB->Free==VB_SIZE)  VB->Free = 1;                \
  264.       }                                                         \
  265.       /* else both verts are inside ==> do nothing */           \
  266.    }
  267.  
  268.  
  269. #define X(I)    coord[I][0]
  270. #define Y(I)    coord[I][1]
  271. #define Z(I)    coord[I][2]
  272. #define W(I)    coord[I][3]
  273.  
  274. /*
  275.  * Begin clipping
  276.  */
  277.  
  278.    /*** Clip against +X side ***/
  279. #define OUTSIDE(K)      (X(K) > W(K))
  280. #define COMPUTE_INTERSECTION( new, in, out )        \
  281.     dx = X(out) - X(in);                \
  282.     dw = W(out) - W(in);                \
  283.     t = (X(in) - W(in)) / (dw-dx);            \
  284.     X(new) = X(in) + t * dx;            \
  285.     Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  286.     Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  287.     W(new) = W(in) + t * dw;
  288.  
  289.    GENERAL_CLIP
  290.  
  291. #undef OUTSIDE
  292. #undef COMPUTE_INTERSECTION
  293.  
  294.  
  295.    /*** Clip against -X side ***/
  296. #define OUTSIDE(K)      (X(K) < -W(K))
  297. #define COMPUTE_INTERSECTION( new, in, out )        \
  298.     dx = X(out) - X(in);                \
  299.     dw = W(out) - W(in);                \
  300.         t = -(X(in) + W(in)) / (dw+dx);            \
  301.     X(new) = X(in) + t * dx;            \
  302.     Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  303.     Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  304.     W(new) = W(in) + t * dw;
  305.  
  306.    GENERAL_CLIP
  307.  
  308. #undef OUTSIDE
  309. #undef COMPUTE_INTERSECTION
  310.  
  311.  
  312.    /*** Clip against +Y side ***/
  313. #define OUTSIDE(K)      (Y(K) > W(K))
  314. #define COMPUTE_INTERSECTION( new, in, out )        \
  315.     dy = Y(out) - Y(in);                \
  316.     dw = W(out) - W(in);                \
  317.         t = (Y(in) - W(in)) / (dw-dy);            \
  318.     X(new) = X(in) + t * (X(out) - X(in));        \
  319.     Y(new) = Y(in) + t * dy;            \
  320.     Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  321.     W(new) = W(in) + t * dw;
  322.  
  323.    GENERAL_CLIP
  324.  
  325. #undef OUTSIDE
  326. #undef COMPUTE_INTERSECTION
  327.  
  328.  
  329.    /*** Clip against -Y side ***/
  330. #define OUTSIDE(K)      (Y(K) < -W(K))
  331. #define COMPUTE_INTERSECTION( new, in, out )        \
  332.         dy = Y(out) - Y(in);                \
  333.         dw = W(out) - W(in);                \
  334.         t = -(Y(in) + W(in)) / (dw+dy);            \
  335.         X(new) = X(in) + t * (X(out) - X(in));        \
  336.     Y(new) = Y(in) + t * dy;            \
  337.     Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  338.     W(new) = W(in) + t * dw;
  339.  
  340.    GENERAL_CLIP
  341.  
  342. #undef OUTSIDE
  343. #undef COMPUTE_INTERSECTION
  344.  
  345.  
  346.    /*** Clip against +Z side ***/
  347. #define OUTSIDE(K)      (Z(K) > W(K))
  348. #define COMPUTE_INTERSECTION( new, in, out )        \
  349.         dz = Z(out) - Z(in);                \
  350.         dw = W(out) - W(in);                \
  351.         t = (Z(in) - W(in)) / (dw-dz);            \
  352.         X(new) = X(in) + t * (X(out) - X(in));        \
  353.         Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  354.     Z(new) = Z(in) + t * dz;            \
  355.     W(new) = W(in) + t * dw;
  356.  
  357.    GENERAL_CLIP
  358.  
  359. #undef OUTSIDE
  360. #undef COMPUTE_INTERSECTION
  361.  
  362.  
  363.    /*** Clip against -Z side ***/
  364. #define OUTSIDE(K)      (Z(K) < -W(K))
  365. #define COMPUTE_INTERSECTION( new, in, out )        \
  366.         dz = Z(out) - Z(in);                \
  367.         dw = W(out) - W(in);                \
  368.         t = -(Z(in) + W(in)) / (dw+dz);            \
  369.         X(new) = X(in) + t * (X(out) - X(in));        \
  370.         Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  371.     Z(new) = Z(in) + t * dz;            \
  372.     W(new) = W(in) + t * dw;
  373.  
  374.    GENERAL_CLIP
  375.  
  376. #undef OUTSIDE
  377. #undef COMPUTE_INTERSECTION
  378.  
  379. #undef GENERAL_CLIP
  380.  
  381.    *i = ii;
  382.    *j = jj;
  383.    return 1;
  384. }
  385.  
  386.  
  387.  
  388.  
  389. /*
  390.  * Clip a polygon against the view volume defined by -w<=x,y,z<=w.
  391.  * Input:  n - number of vertices in input polygon.
  392.  *         vlist - list of indexes into VB->V* of polygon to clip.
  393.  * Output:  vlist - modified list of vertex indexes
  394.  * Return:  number of vertices in resulting polygon
  395.  */
  396. GLuint gl_viewclip_polygon( GLcontext* ctx, GLuint n, GLuint vlist[] )
  397.  
  398. {
  399.    struct vertex_buffer* VB = ctx->VB;
  400.    GLfloat (*coord)[4] = VB->Clip;
  401.  
  402.    GLuint previ, prevj;
  403.    GLuint curri, currj;
  404.    GLuint vlist2[VB_SIZE];
  405.    GLuint n2;
  406.    GLdouble dx, dy, dz, dw, t, neww;
  407.  
  408.    Space = CLIP_SPACE;
  409.  
  410. /*
  411.  * We use 6 instances of this code to implement clipping against the
  412.  * 6 sides of the view volume.  Prior to each we define the macros:
  413.  *    INLIST = array which lists input vertices
  414.  *    OUTLIST = array which lists output vertices
  415.  *    INCOUNT = variable which is the number of vertices in INLIST[]
  416.  *    OUTCOUNT = variable which is the number of vertices in OUTLIST[]
  417.  *    INSIDE(i) = test if vertex v[i] is inside the view volume
  418.  *    COMPUTE_INTERSECTION(in,out,new) = compute intersection of line
  419.  *              from v[in] to v[out] with the clipping plane and store
  420.  *              the result in v[new]
  421.  */
  422.  
  423. #define GENERAL_CLIP                                                    \
  424.    if (INCOUNT<3)  return 0;                        \
  425.    previ = INCOUNT-1;        /* let previous = last vertex */    \
  426.    prevj = INLIST[previ];                        \
  427.    OUTCOUNT = 0;                                                        \
  428.    for (curri=0;curri<INCOUNT;curri++) {                \
  429.       currj = INLIST[curri];                        \
  430.       if (INSIDE(currj)) {                        \
  431.          if (INSIDE(prevj)) {                        \
  432.             /* both verts are inside ==> copy current to outlist */     \
  433.         OUTLIST[OUTCOUNT] = currj;                    \
  434.         OUTCOUNT++;                            \
  435.          }                                                              \
  436.          else {                                                         \
  437.             /* current is inside and previous is outside ==> clip */    \
  438.         COMPUTE_INTERSECTION( currj, prevj,    VB->Free )        \
  439.         /* if new point not coincident with previous point... */    \
  440.         if (t>0.0) {                        \
  441.            /* interpolate aux info using the value of t */        \
  442.            if (ctx->ClipMask)                    \
  443.           interpolate_aux( ctx, VB->Free, t, currj, prevj );    \
  444.            VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];        \
  445.            /* output new point */                    \
  446.            OUTLIST[OUTCOUNT] = VB->Free;                \
  447.            VB->Free++;                        \
  448.            if (VB->Free==VB_SIZE)   VB->Free = 1;            \
  449.            OUTCOUNT++;                        \
  450.         }                                \
  451.         /* Output current */                    \
  452.         OUTLIST[OUTCOUNT] = currj;                    \
  453.         OUTCOUNT++;                            \
  454.          }                                                              \
  455.       }                                                                 \
  456.       else {                                                            \
  457.          if (INSIDE(prevj)) {                        \
  458.             /* current is outside and previous is inside ==> clip */    \
  459.         COMPUTE_INTERSECTION( prevj, currj, VB->Free )        \
  460.         /* if new point not coincident with previous point... */    \
  461.         if (t>0.0) {                        \
  462.            /* interpolate aux info using the value of t */        \
  463.            if (ctx->ClipMask)                    \
  464.           interpolate_aux( ctx, VB->Free, t, prevj, currj );    \
  465.            VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];        \
  466.            /* output new point */                    \
  467.            OUTLIST[OUTCOUNT] = VB->Free;                \
  468.            VB->Free++;                        \
  469.            if (VB->Free==VB_SIZE)   VB->Free = 1;            \
  470.            OUTCOUNT++;                        \
  471.         }                                \
  472.          }                                \
  473.          /* else both verts are outside ==> do nothing */        \
  474.       }                                    \
  475.       /* let previous = current */                    \
  476.       previ = curri;                            \
  477.       prevj = currj;                            \
  478.       /* check for overflowing vertex buffer */                \
  479.       if (OUTCOUNT>=VB_SIZE-1) {                    \
  480.      /* Too many vertices */                    \
  481.          if (OUTLIST==vlist2) {                        \
  482.         /* copy OUTLIST[] to vlist[] */                \
  483.         int i;                            \
  484.         for (i=0;i<VB_SIZE;i++) {                    \
  485.            vlist[i] = OUTLIST[i];                    \
  486.         }                                \
  487.      }                                \
  488.      return VB_SIZE-1;                        \
  489.       }                                    \
  490.    }
  491.  
  492.  
  493. #define X(I)    coord[I][0]
  494. #define Y(I)    coord[I][1]
  495. #define Z(I)    coord[I][2]
  496. #define W(I)    coord[I][3]
  497.  
  498. /*
  499.  * Clip against +X
  500.  */
  501. #define INCOUNT n
  502. #define OUTCOUNT n2
  503. #define INLIST vlist
  504. #define OUTLIST vlist2
  505. #define INSIDE(K)      (X(K) <= W(K))
  506.  
  507. #define COMPUTE_INTERSECTION( in, out, new )        \
  508.         dx = X(out) - X(in);                \
  509.         dw = W(out) - W(in);                \
  510.         t = (X(in)-W(in)) / (dw-dx);            \
  511.     neww = W(in) + t * dw;                \
  512.     X(new) = neww;                    \
  513.     Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  514.     Z(new) = Z(in) + t * (Z(out) - Z(in));         \
  515.     W(new) = neww;
  516.  
  517.    GENERAL_CLIP
  518.  
  519. #undef INCOUNT
  520. #undef OUTCOUNT
  521. #undef INLIST
  522. #undef OUTLIST
  523. #undef INSIDE
  524. #undef COMPUTE_INTERSECTION
  525.  
  526.  
  527. /*
  528.  * Clip against -X
  529.  */
  530. #define INCOUNT n2
  531. #define OUTCOUNT n
  532. #define INLIST vlist2
  533. #define OUTLIST vlist
  534. #define INSIDE(K)       (X(K) >= -W(K))
  535. #define COMPUTE_INTERSECTION( in, out, new )        \
  536.         dx = X(out)-X(in);                          \
  537.         dw = W(out)-W(in);                          \
  538.         t = -(X(in)+W(in)) / (dw+dx);               \
  539.     neww = W(in) + t * dw;                \
  540.         X(new) = -neww;                    \
  541.         Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  542.         Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  543.         W(new) = neww;
  544.  
  545.    GENERAL_CLIP
  546.  
  547. #undef INCOUNT
  548. #undef OUTCOUNT
  549. #undef INLIST
  550. #undef OUTLIST
  551. #undef INSIDE
  552. #undef COMPUTE_INTERSECTION
  553.  
  554.  
  555. /*
  556.  * Clip against +Y
  557.  */
  558. #define INCOUNT n
  559. #define OUTCOUNT n2
  560. #define INLIST vlist
  561. #define OUTLIST vlist2
  562. #define INSIDE(K)       (Y(K) <= W(K))
  563. #define COMPUTE_INTERSECTION( in, out, new )        \
  564.         dy = Y(out)-Y(in);                          \
  565.         dw = W(out)-W(in);                          \
  566.         t = (Y(in)-W(in)) / (dw-dy);                \
  567.     neww = W(in) + t * dw;                 \
  568.         X(new) = X(in) + t * (X(out) - X(in));        \
  569.         Y(new) = neww;                    \
  570.         Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  571.         W(new) = neww;
  572.  
  573.    GENERAL_CLIP
  574.  
  575. #undef INCOUNT
  576. #undef OUTCOUNT
  577. #undef INLIST
  578. #undef OUTLIST
  579. #undef INSIDE
  580. #undef COMPUTE_INTERSECTION
  581.  
  582.  
  583. /*
  584.  * Clip against -Y
  585.  */
  586. #define INCOUNT n2
  587. #define OUTCOUNT n
  588. #define INLIST vlist2
  589. #define OUTLIST vlist
  590. #define INSIDE(K)       (Y(K) >= -W(K))
  591. #define COMPUTE_INTERSECTION( in, out, new )        \
  592.         dy = Y(out)-Y(in);                          \
  593.         dw = W(out)-W(in);                          \
  594.         t = -(Y(in)+W(in)) / (dw+dy);               \
  595.     neww = W(in) + t * dw;                \
  596.         X(new) = X(in) + t * (X(out) - X(in));        \
  597.         Y(new) = -neww;                    \
  598.         Z(new) = Z(in) + t * (Z(out) - Z(in));        \
  599.         W(new) = neww;
  600.  
  601.    GENERAL_CLIP
  602.  
  603. #undef INCOUNT
  604. #undef OUTCOUNT
  605. #undef INLIST
  606. #undef OUTLIST
  607. #undef INSIDE
  608. #undef COMPUTE_INTERSECTION
  609.  
  610.  
  611.  
  612. /*
  613.  * Clip against +Z
  614.  */
  615. #define INCOUNT n
  616. #define OUTCOUNT n2
  617. #define INLIST vlist
  618. #define OUTLIST vlist2
  619. #define INSIDE(K)       (Z(K) <= W(K))
  620. #define COMPUTE_INTERSECTION( in, out, new )        \
  621.         dz = Z(out)-Z(in);                          \
  622.         dw = W(out)-W(in);                          \
  623.         t = (Z(in)-W(in)) / (dw-dz);                \
  624.     neww = W(in) + t * dw;                \
  625.         X(new) = X(in) + t * (X(out) - X(in));        \
  626.         Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  627.         Z(new) = neww;                    \
  628.         W(new) = neww;
  629.  
  630.    GENERAL_CLIP
  631.  
  632. #undef INCOUNT
  633. #undef OUTCOUNT
  634. #undef INLIST
  635. #undef OUTLIST
  636. #undef INSIDE
  637. #undef COMPUTE_INTERSECTION
  638.  
  639.  
  640. /*
  641.  * Clip against -Z
  642.  */
  643. #define INCOUNT n2
  644. #define OUTCOUNT n
  645. #define INLIST vlist2
  646. #define OUTLIST vlist
  647. #define INSIDE(K)       (Z(K) >= -W(K))
  648. #define COMPUTE_INTERSECTION( in, out, new )        \
  649.         dz = Z(out)-Z(in);                          \
  650.         dw = W(out)-W(in);                          \
  651.         t = -(Z(in)+W(in)) / (dw+dz);               \
  652.     neww = W(in) + t * dw;                \
  653.         X(new) = X(in) + t * (X(out) - X(in));        \
  654.         Y(new) = Y(in) + t * (Y(out) - Y(in));        \
  655.         Z(new) = -neww;                    \
  656.         W(new) = neww;
  657.  
  658.    GENERAL_CLIP
  659.  
  660. #undef INCOUNT
  661. #undef INLIST
  662. #undef OUTLIST
  663. #undef INSIDE
  664. #undef COMPUTE_INTERSECTION
  665.  
  666.    /* 'OUTCOUNT' clipped vertices are now back in v[] */
  667.    return OUTCOUNT;
  668.  
  669. #undef GENERAL_CLIP
  670. #undef OUTCOUNT
  671. }
  672.  
  673.  
  674.  
  675.  
  676. /**********************************************************************/
  677. /*         Clipping against user-defined clipping planes.             */
  678. /**********************************************************************/
  679.  
  680.  
  681.  
  682. /*
  683.  * If the dot product of the eye coordinates of a vertex with the
  684.  * stored plane equation components is positive or zero, the vertex
  685.  * is in with respect to that clipping plane, otherwise it is out.
  686.  */
  687.  
  688.  
  689.  
  690. /*
  691.  * Clip a point against the user clipping planes.
  692.  * Input:  v - vertex-vector describing the point to clip.
  693.  * Return:  0 = point was clipped
  694.  *          1 = point not clipped
  695.  */
  696. GLuint gl_userclip_point( GLcontext* ctx, const GLfloat v[] )
  697. {
  698.    GLuint p;
  699.  
  700.    for (p=0;p<MAX_CLIP_PLANES;p++) {
  701.       if (ctx->Transform.ClipEnabled[p]) {
  702.      GLfloat dot = v[0] * ctx->Transform.ClipEquation[p][0]
  703.              + v[1] * ctx->Transform.ClipEquation[p][1]
  704.              + v[2] * ctx->Transform.ClipEquation[p][2]
  705.              + v[3] * ctx->Transform.ClipEquation[p][3];
  706.          if (dot < 0.0F) {
  707.             return 0;
  708.          }
  709.       }
  710.    }
  711.  
  712.    return 1;
  713. }
  714.  
  715.  
  716. #define MAGIC_NUMBER -0.8e-03F
  717.  
  718.  
  719. /* Test if VB->Eye[J] is inside the clipping plane defined by A,B,C,D */
  720. #define INSIDE( J, A, B, C, D )                   \
  721.    ( (VB->Eye[J][0] * A + VB->Eye[J][1] * B            \
  722.     + VB->Eye[J][2] * C + VB->Eye[J][3] * D) >= MAGIC_NUMBER )
  723.  
  724.  
  725. /* Test if VB->Eye[J] is outside the clipping plane defined by A,B,C,D */
  726. #define OUTSIDE( J, A, B, C, D )                   \
  727.    ( (VB->Eye[J][0] * A + VB->Eye[J][1] * B            \
  728.     + VB->Eye[J][2] * C + VB->Eye[J][3] * D) < MAGIC_NUMBER )
  729.  
  730.  
  731. /*
  732.  * Clip a line against the user clipping planes.
  733.  * Input:  i, j - indexes into VB->V*[] of endpoints
  734.  * Output:  i, j - indexes into VB->V*[] of (possibly clipped) endpoints
  735.  * Return:  0 = line completely clipped
  736.  *          1 = line is visible
  737.  */
  738. GLuint gl_userclip_line( GLcontext* ctx, GLuint *i, GLuint *j )
  739. {
  740.    struct vertex_buffer* VB = ctx->VB;
  741.  
  742.    GLuint p, ii, jj;
  743.  
  744.    Space = EYE_SPACE;
  745.  
  746.    ii = *i;
  747.    jj = *j;
  748.  
  749.    for (p=0;p<MAX_CLIP_PLANES;p++) {
  750.       if (ctx->Transform.ClipEnabled[p]) {
  751.      register GLfloat a, b, c, d;
  752.      a = ctx->Transform.ClipEquation[p][0];
  753.      b = ctx->Transform.ClipEquation[p][1];
  754.      c = ctx->Transform.ClipEquation[p][2];
  755.      d = ctx->Transform.ClipEquation[p][3];
  756.  
  757.          if (OUTSIDE( ii, a,b,c,d  )) {
  758.             if (OUTSIDE( jj, a,b,c,d )) {
  759.                /* ii and jj outside ==> quit */
  760.                return 0;
  761.             }
  762.             else {
  763.                /* ii is outside, jj is inside ==> clip */
  764.                GLfloat dx, dy, dz, dw, t, denom;
  765.                dx = VB->Eye[ii][0] - VB->Eye[jj][0];
  766.                dy = VB->Eye[ii][1] - VB->Eye[jj][1];
  767.                dz = VB->Eye[ii][2] - VB->Eye[jj][2];
  768.                dw = VB->Eye[ii][3] - VB->Eye[jj][3];
  769.            denom = dx*a + dy*b + dz*c + dw*d;
  770.            if (denom==0.0) {
  771.           t = 0.0;
  772.            }
  773.            else {
  774.           t = -(VB->Eye[jj][0]*a+VB->Eye[jj][1]*b
  775.                +VB->Eye[jj][2]*c+VB->Eye[jj][3]*d) / denom;
  776.                   if (t>1.0F)  t = 1.0F;
  777.            }
  778.            VB->Eye[VB->Free][0] = VB->Eye[jj][0] + t * dx;
  779.            VB->Eye[VB->Free][1] = VB->Eye[jj][1] + t * dy;
  780.            VB->Eye[VB->Free][2] = VB->Eye[jj][2] + t * dz;
  781.            VB->Eye[VB->Free][3] = VB->Eye[jj][3] + t * dw;
  782.  
  783.            /* Interpolate colors, indexes, and/or texture coords */
  784.            if (ctx->ClipMask)
  785.           interpolate_aux( ctx, VB->Free, t, jj, ii );
  786.  
  787.            ii = VB->Free;
  788.            VB->Free++;
  789.            if (VB->Free==VB_SIZE)   VB->Free = 1;
  790.             }
  791.          }
  792.          else {
  793.             if (OUTSIDE( jj, a,b,c,d )) {
  794.                /* ii is inside, jj is outside ==> clip */
  795.                GLfloat dx, dy, dz, dw, t, denom;
  796.                dx = VB->Eye[jj][0] - VB->Eye[ii][0];
  797.                dy = VB->Eye[jj][1] - VB->Eye[ii][1];
  798.                dz = VB->Eye[jj][2] - VB->Eye[ii][2];
  799.                dw = VB->Eye[jj][3] - VB->Eye[ii][3];
  800.            denom = dx*a + dy*b + dz*c + dw*d;
  801.            if (denom==0.0) {
  802.           t = 0.0;
  803.            }
  804.            else {
  805.           t = -(VB->Eye[ii][0]*a+VB->Eye[ii][1]*b
  806.                +VB->Eye[ii][2]*c+VB->Eye[ii][3]*d) / denom;
  807.                   if (t>1.0F)  t = 1.0F;
  808.            }
  809.            VB->Eye[VB->Free][0] = VB->Eye[ii][0] + t * dx;
  810.            VB->Eye[VB->Free][1] = VB->Eye[ii][1] + t * dy;
  811.            VB->Eye[VB->Free][2] = VB->Eye[ii][2] + t * dz;
  812.            VB->Eye[VB->Free][3] = VB->Eye[ii][3] + t * dw;
  813.  
  814.            /* Interpolate colors, indexes, and/or texture coords */
  815.            if (ctx->ClipMask)
  816.           interpolate_aux( ctx, VB->Free, t, ii, jj );
  817.  
  818.            jj = VB->Free;
  819.            VB->Free++;
  820.            if (VB->Free==VB_SIZE)   VB->Free = 1;
  821.             }
  822.             else {
  823.                /* ii and jj inside ==> do nothing */
  824.             }
  825.          }
  826.       }
  827.    }
  828.  
  829.    *i = ii;
  830.    *j = jj;
  831.    return 1;
  832. }
  833.  
  834.  
  835.  
  836.  
  837. /*
  838.  * Clip a polygon against the user clipping planes defined in eye coordinates.
  839.  * Input:  n - number of vertices.
  840.  *         vlist - list of vertices in input polygon.
  841.  * Output:  vlist - list of vertices in output polygon.
  842.  * Return:  number of vertices after clipping.
  843.  */
  844. GLuint gl_userclip_polygon( GLcontext* ctx, GLuint n, GLuint vlist[] )
  845. {
  846.    struct vertex_buffer* VB = ctx->VB;
  847.  
  848.    GLuint vlist2[VB_SIZE];
  849.    GLuint *inlist, *outlist;
  850.    GLuint incount, outcount;
  851.    GLuint curri, currj;
  852.    GLuint previ, prevj;
  853.    GLuint p;
  854.  
  855.    Space = EYE_SPACE;
  856.  
  857.    /* initialize input vertex list */
  858.    incount = n;
  859.    inlist = vlist;
  860.    outlist = vlist2;
  861.  
  862.    for (p=0;p<MAX_CLIP_PLANES;p++) {
  863.       if (ctx->Transform.ClipEnabled[p]) {
  864.      register float a = ctx->Transform.ClipEquation[p][0];
  865.      register float b = ctx->Transform.ClipEquation[p][1];
  866.      register float c = ctx->Transform.ClipEquation[p][2];
  867.      register float d = ctx->Transform.ClipEquation[p][3];
  868.  
  869.      if (incount<3)  return 0;
  870.  
  871.      /* initialize prev to be last in the input list */
  872.      previ = incount - 1;
  873.      prevj = inlist[previ];
  874.  
  875.          outcount = 0;
  876.  
  877.          for (curri=0;curri<incount;curri++) {
  878.         currj = inlist[curri];
  879.  
  880.             if (INSIDE(currj, a,b,c,d)) {
  881.                if (INSIDE(prevj, a,b,c,d)) {
  882.                   /* both verts are inside ==> copy current to outlist */
  883.           outlist[outcount++] = currj;
  884.                }
  885.                else {
  886.                   /* current is inside and previous is outside ==> clip */
  887.                   GLfloat dx, dy, dz, dw, t, denom;
  888.           /* compute t */
  889.           dx = VB->Eye[prevj][0] - VB->Eye[currj][0];
  890.           dy = VB->Eye[prevj][1] - VB->Eye[currj][1];
  891.           dz = VB->Eye[prevj][2] - VB->Eye[currj][2];
  892.           dw = VB->Eye[prevj][3] - VB->Eye[currj][3];
  893.           denom = dx*a + dy*b + dz*c + dw*d;
  894.           if (denom==0.0) {
  895.              t = 0.0;
  896.           }
  897.           else {
  898.              t = -(VB->Eye[currj][0]*a+VB->Eye[currj][1]*b
  899.                +VB->Eye[currj][2]*c+VB->Eye[currj][3]*d) / denom;
  900.                      if (t>1.0F) {
  901.                         t = 1.0F;
  902.                      }
  903.           }
  904.           /* interpolate new vertex position */
  905.           VB->Eye[VB->Free][0] = VB->Eye[currj][0] + t*dx;
  906.           VB->Eye[VB->Free][1] = VB->Eye[currj][1] + t*dy;
  907.           VB->Eye[VB->Free][2] = VB->Eye[currj][2] + t*dz;
  908.           VB->Eye[VB->Free][3] = VB->Eye[currj][3] + t*dw;
  909.  
  910.           /* interpolate color, index, and/or texture coord */
  911.           if (ctx->ClipMask) {
  912.              interpolate_aux( ctx, VB->Free, t, currj, prevj);
  913.           }
  914.           VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];
  915.  
  916.           /* output new vertex */
  917.           outlist[outcount++] = VB->Free;
  918.           VB->Free++;
  919.           if (VB->Free==VB_SIZE)   VB->Free = 1;
  920.           /* output current vertex */
  921.           outlist[outcount++] = currj;
  922.                }
  923.             }
  924.             else {
  925.                if (INSIDE(prevj, a,b,c,d)) {
  926.                   /* current is outside and previous is inside ==> clip */
  927.                   GLfloat dx, dy, dz, dw, t, denom;
  928.           /* compute t */
  929.                   dx = VB->Eye[currj][0]-VB->Eye[prevj][0];
  930.                   dy = VB->Eye[currj][1]-VB->Eye[prevj][1];
  931.                   dz = VB->Eye[currj][2]-VB->Eye[prevj][2];
  932.                   dw = VB->Eye[currj][3]-VB->Eye[prevj][3];
  933.           denom = dx*a + dy*b + dz*c + dw*d;
  934.           if (denom==0.0) {
  935.              t = 0.0;
  936.           }
  937.           else {
  938.              t = -(VB->Eye[prevj][0]*a+VB->Eye[prevj][1]*b
  939.                +VB->Eye[prevj][2]*c+VB->Eye[prevj][3]*d) / denom;
  940.                      if (t>1.0F) {
  941.                         t = 1.0F;
  942.                      }
  943.           }
  944.           /* interpolate new vertex position */
  945.           VB->Eye[VB->Free][0] = VB->Eye[prevj][0] + t*dx;
  946.           VB->Eye[VB->Free][1] = VB->Eye[prevj][1] + t*dy;
  947.           VB->Eye[VB->Free][2] = VB->Eye[prevj][2] + t*dz;
  948.           VB->Eye[VB->Free][3] = VB->Eye[prevj][3] + t*dw;
  949.  
  950.           /* interpolate color, index, and/or texture coord */
  951.           if (ctx->ClipMask) {
  952.              interpolate_aux( ctx, VB->Free, t, prevj, currj);
  953.           }
  954.           VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];
  955.  
  956.           /* output new vertex */
  957.           outlist[outcount++] = VB->Free;
  958.           VB->Free++;
  959.           if (VB->Free==VB_SIZE)   VB->Free = 1;
  960.            }
  961.                /* else  both verts are outside ==> do nothing */
  962.             }
  963.  
  964.         previ = curri;
  965.         prevj = currj;
  966.  
  967.         /* check for overflowing vertex buffer */
  968.             if (outcount>=VB_SIZE-1) {
  969.                /* Too many vertices */
  970.                if (outlist!=vlist2) {
  971.                   MEMCPY( vlist, vlist2, outcount * sizeof(GLuint) );
  972.                }
  973.                return VB_SIZE-1;
  974.             }
  975.  
  976.          }  /* for i */
  977.  
  978.          /* swap inlist and outlist pointers */
  979.          {
  980.             GLuint *tmp;
  981.             tmp = inlist;
  982.             inlist = outlist;
  983.             outlist = tmp;
  984.             incount = outcount;
  985.          }
  986.  
  987.       } /* if */
  988.    } /* for p */
  989.  
  990.    /* outlist points to the list of vertices resulting from the last */
  991.    /* clipping.  If outlist == vlist2 then we have to copy the vertices */
  992.    /* back to vlist */
  993.    if (outlist!=vlist2) {
  994.       MEMCPY( vlist, vlist2, outcount * sizeof(GLuint) );
  995.    }
  996.  
  997.    return outcount;
  998. }
  999.  
  1000.